﻿//#define TRACE_1
//#define TRACE_2
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ProjectEulerSolutions.Problems
{
    /*
     * Let pn be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (pn−1)n + (pn+1)n is divided by pn2.

For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.

The least value of n for which the remainder first exceeds 109 is 7037.

Find the least value of n for which the remainder first exceeds 1010.

     * */
    class Problem123 : IProblem
    {
        public string Calculate()
        {
            long limit = 10000000000;
            long[] p = new long[100000];
            p[0] = 2;

            SieveOfAtkin sieve = new SieveOfAtkin(1000000);
            for (int i = 1, j = 3; i < p.Length; i++)
            {
                while (!sieve.IsPrime(j))
                    j += 2;
                p[i] = j;
                j += 2;
            }

            for (int n = 5; n <= p.Length; n+=2)
            {
                long r = 2 * n * p[n - 1];
#if TRACE_1
                Console.WriteLine("n={0}, pn={1}, r={2}", n, p[n - 1], r);
                Console.ReadKey();
#endif
                if (2 * n >= p[n - 1])
                    Console.WriteLine("n={0} > pn={1}", n, p[n - 1]);

                if (r > limit)
                {
#if TRACE_2
                    Console.WriteLine("n={0}, pn={1}, r={2}", n, p[n - 1], r);
                    Console.WriteLine("((pn - 1)^n + (pn + 1)^n) mod pn^2 = r");
                    Console.WriteLine("(({0} - 1)^{1} + ({0} + 1)^{1}) mod {0}^2 = r", p[n - 1], n);
                    Console.WriteLine("({0}^{2} + {1}^{2}) mod {3}^2 = r", p[n - 1] - 1, p[n - 1] + 1, n, p[n - 1]);
                    Console.WriteLine("({0} + {1}) mod {2} = r", BigInteger.Pow(p[n - 1] - 1, n), BigInteger.Pow(p[n - 1] + 1, n), p[n - 1] * p[n - 1]);
                    Console.WriteLine("{0} mod {1} = {2}", BigInteger.Pow(p[n - 1] - 1, n) + BigInteger.Pow(p[n - 1] + 1, n), p[n - 1] * p[n - 1], (BigInteger.Pow(p[n - 1] - 1, n) + BigInteger.Pow(p[n - 1] + 1, n)) % (p[n - 1] * p[n - 1]));
#endif
                    return n.ToString();
                }
            }

            return "Nije nadjeno";
        }
    }
}
